#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

//Minimum size of palindrome
#define minSzNPalindrome 3
#define MIN(x,y) (((x)<(y))?(x):(y))

typedef size_t iter_t;

//Datatype to gather all algorithm Manacher requirements
typedef struct preProcessedObject
{
	char* strWithSpaces;
	size_t sizeWithSpaces;
	char* strWithoutSpaces;
	size_t sizeWithoutSpaces;
	
	int* lettersPositions;
} PreProcessedObject;

enum algorithmId {BRUTE_FORCE,MANACHER};

//If a character is invalid returns blank space otherwise returns lowercase character
char ProcessChar(char c)
{
	if(islower(c))
		return c;
	else if(isalpha(c))
		return tolower(c);
	return ' ';
}

//Removing nonalpha characters
PreProcessedObject* Preprocess(char* buffer,size_t size)
{
	PreProcessedObject* obj;
	obj=(PreProcessedObject*)malloc(sizeof(PreProcessedObject));

	char* strWithSpaces;
	char* strWithoutSpaces;
	int* positionsWithoutSpaces;

	strWithSpaces=(char*)malloc(sizeof(char)*size);
	strWithoutSpaces=(char*)malloc(sizeof(char)*size);
	positionsWithoutSpaces=(int*)malloc(sizeof(int)*size);
	
	iter_t I;
	size_t J_ce,J_se;
	J_ce=J_se=0;

	strWithSpaces[J_ce++]=' ';

	//This flag help us in case there are a sequence of blank spaces, only one is left
	int flagSpaceFound=0;
	for(I=0;I<size;I++)
	{
		char c=ProcessChar(buffer[I]);
		if(c==' '&&flagSpaceFound==0)
		{
			strWithSpaces[J_ce++]=c;
			flagSpaceFound=1;
		}
		else if(c!=' ')
		{
			positionsWithoutSpaces[J_se]=J_ce-1;
			strWithSpaces[J_ce++]=c;
			strWithoutSpaces[J_se++]=c;
			flagSpaceFound=0;
		}
	}

	strWithSpaces[J_ce]='\0';
	strWithoutSpaces[J_se]='\0';
	
	obj->strWithSpaces=strWithSpaces;
	obj->sizeWithSpaces=J_ce;
	obj->strWithoutSpaces=strWithoutSpaces;
	obj->sizeWithoutSpaces=J_se;
	obj->lettersPositions=positionsWithoutSpaces;
	return obj;
}

//Print string of range [i,j]
void PrintRange(char* str,iter_t i,iter_t j)
{
	char tmp=str[j];
	str[j]='\0';
	printf("%s\n",&str[i+1]);
	str[j]=tmp;
}

//This naive algorithm finds for one or more word composed palindromes on an iterator centered
void BruteForceAlgorithm(char* str,size_t size)
{
	iter_t I;
	//Finding palindromes between a disjoint range
	for(I=0;I<size;I++)
	{
		//Left and right index iterators
		iter_t l=I,r=I;

		//Finding odd palindromes
		while(l>=0&&r<=size-1)
		{
			if(str[l]==str[r])
			{
				l--;
				r++;
			}
			else if(str[l]==' ')
				l--;
			else if(str[r]==' ')
				r++;
			else
				break;
		}
	
		//Print palindrome if the palindrome range is between spaces and its size is bigger than minimum size
		if((r-l)-2>minSzNPalindrome&&str[l+1]==' '&&str[r-1]==' ')
			PrintRange(str,l+1,r-1);
		
		//Finding even palindromes
		l=I,r=I+1;
		
		//Avoids palindromes with beginning and ending spaces
		if(str[l]!=' '&&' '!=str[r])
		while(l>=0&&r<=size-1)
		{
			if(str[l]==str[r])
			{
				l--;
				r++;
			}
			else if(str[l]==' ')
				l--;
			else if(str[r]==' ')
				r++;
			else
				break;
		}
		
		//Print palindrome if the palindrome range is between spaces and its size is bigger than minimum size
		if((r-l)-2>minSzNPalindrome&&str[l+1]==' '&&str[r-1]==' ')
			PrintRange(str,l+1,r-1);
	}
}

int ManacherAlgorithm(char* str,size_t size,int* lettersPositions,char* strWithSpaces)
{
	int* symmetryValues;
	size_t sizePreProcessedStr;
	char* preProcessedStr;

	sizePreProcessedStr=size*2+2;
	//Allocating memory for auxiliar arrays
	symmetryValues=(int*)malloc(sizeof(int)*sizePreProcessedStr);
	preProcessedStr=(char*)malloc(sizeof(char)*sizePreProcessedStr);

	preProcessedStr[0]='$';
	preProcessedStr[1]='#';
	
	//Preparing string with '#' and '$' delimitators
	unsigned I;
	for(I=2;I<sizePreProcessedStr;I+=2)
	{
		preProcessedStr[I]=str[I/2-1];
		preProcessedStr[I+1]='#';
	}

	iter_t R=0,CENTER=0;
	memset(symmetryValues,0,sizePreProcessedStr);

	//Updating symmetric values
	for(I=1;I<sizePreProcessedStr;I++)
	{
		if(R>I)
			symmetryValues[I]=MIN(symmetryValues[2*CENTER-I],R-I);
		else
			symmetryValues[I]=1;
	
		for(;preProcessedStr[I-symmetryValues[I]]==preProcessedStr[I+symmetryValues[I]];symmetryValues[I]++);

		if(I+symmetryValues[I]>R)
		{
			R=I+symmetryValues[I];
			CENTER=I;
		}
	}

	//Goes over entire auxiliar symmetryValues array to print palindromes strings
	for(I=0;I<sizePreProcessedStr;I++)
		if((symmetryValues[I]-1)>=minSzNPalindrome)
			if(strWithSpaces[lettersPositions[I/2-symmetryValues[I]/2]]==' '&&strWithSpaces[lettersPositions[I/2-symmetryValues[I]/2+symmetryValues[I]-1]]==' ')
				PrintRange(strWithSpaces,lettersPositions[I/2-symmetryValues[I]/2],lettersPositions[I/2-symmetryValues[I]/2+symmetryValues[I]-1]);

	free(symmetryValues);
	free(preProcessedStr);
	return 0;
}

int main(int argc,char** argv)
{
	char nameFile[255];
	int algorithmId=0;

	if(argc>1)
	{
		sscanf(argv[1],"%s",nameFile);
		if(argc==3)
			sscanf(argv[2],"%d",&algorithmId);
	}
	else
	{
		fprintf(stderr,"File is not set!\n");
		return 1;
	}
	
	FILE* inputFile;
	inputFile=fopen(nameFile,"r");
	
	if(inputFile==NULL)
	{
		fprintf(stderr,"Error opening file!\n");
		return 1;
	}
	
	char* inputBuffer;
	//File size
	size_t fSize;
	
	fseek(inputFile,0,SEEK_END);
	fSize=ftell(inputFile);
	rewind(inputFile);
	
	inputBuffer=(char*)malloc(sizeof(char)*fSize);
	
	size_t bytesRead;
	bytesRead=fread(inputBuffer,1,fSize,inputFile);
		
	if(bytesRead!=fSize)
	{
		fprintf(stderr,"Memory error!\n");
		return 1;
	}
		
	PreProcessedObject* obj;
	//Preprocess data read from file
	obj=Preprocess(inputBuffer,fSize);

	if(algorithmId==BRUTE_FORCE)
		BruteForceAlgorithm(obj->strWithSpaces,obj->sizeWithSpaces);
	else if(algorithmId==MANACHER)
		ManacherAlgorithm(obj->strWithoutSpaces,obj->sizeWithoutSpaces,obj->lettersPositions,obj->strWithSpaces);

	return 0;
}
